package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.y19.m03.Node;

/**
 * 116. 填充每个节点的下一个右侧节点指针
 * 
 * https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
 * 
 * @author jie.deng
 *
 */
class Question0116Solution01 {
	
	public Node connect(Node root) {
		if (root == null) {
			return root;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Node> list = new ArrayList<>();
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				list.add(node);
				if (node.left != null && node.right != null) {
					queue.offer(node.left);
					queue.offer(node.right);
				}
			}
			for (int i = 0; i < list.size() - 1; i++) {
				list.get(i).next = list.get(i + 1);
			}
		}
		return root;
	}
    
}